package d2_final_exam.d6_sixth_question;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MyLinkedList03<E extends Comparable> {
    //封装一个链表
    Node<E> head = null;

    //1、首先定义一个私有的内部类, 作为链表的结点
    public static class Node<E> {
        E data;
        Node<E> next;

        //1.提供有参构造器
        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    //2、开发一个添加数据的方法
    public Node<E> add(E e) {
        //1.首先判断当前链表是否是第一次添加数据
        if (head == null) {
            //2.是直接创建一个姓节点,赋值给偷指针
            head = new Node<>(e, null);
        } else {
            //3.不是第一次添加元素。(尾插法)
            //首先保护图指针
            Node<E> temp = head;

            //然temp走到最后
            while (temp.next != null) {
                temp = temp.next;
            }
            //把当前节点创建出来,加到尾部节点
            temp.next = new Node<>(e, null);
        }
        return head;
    }

    //3、首先开发一个sort的方法,对链表进行升序排序
    //每个对象已经封装了head,不需要进行传head进来
    public Node<E> sort() {
        //1.极端判断
        if (head == null) {
            return null;//直接不进行排序
        }
        //2.准备一个集合用于存储,链表中的数据
        List<E> numbers = new ArrayList<>();
        //3.保护头指针
        Node<E> temp = head;
        //4.开始遍历,链表在,将链表中的数据存入到集合中去
        while (temp != null) {
            numbers.add(temp.data);
            temp = temp.next;
        }
        //5.对集合进行排序,使用工具类Collections
        Collections.sort(numbers);//报错是因为,不知道排序规则,既然官方可以进排序,我们亦可以,无非就是实现Comparable

        //6.再次开始保护头结点
        Node<E> temp2 = head;
        //7.循环将数据存储到到链表中去
        for (E number : numbers) {
            temp2.data = number;
            temp2 = temp2.next;
        }

        //7.将头结点进行返回
        return head;
    }

    //4、开放mergeSort方法,支持将两个升序排序的链表,
    //再次合并成一个新链表,要求新链表的结点仍然是递增排序
    //形参列表:需要传递排序的非调用者的头指针
    //返回值类型: 返回新链表的头指针
    public Node<E> mergeSort(Node<E> otherHead) {
        //3.极端判断
        if (head == null && otherHead == null) {
            //不进行合并
            return head;

        }
        if (head != null && otherHead == null) {
            //不合并
            return head;
        }
        if (head == null && otherHead != null) {
            //不合并
            return otherHead;
        }


        if (head != null && otherHead != null) {
            //1.首先创建一个新链表
            Node<E> newHead = new Node<>(null, null);
            //4.在定义一个节点,用于记录新链表的头指针
            Node<E> okNewHead = newHead;
            // 2.定义两个指针,分别在两个链表的头开始遍历,让着两个指针指向的数据进行比较,小的就加入到新链表中,然后小的指针就往下挪
            Node<E> temp1 = head;
            Node<E> temp2 = otherHead;

            //5.循环开始比较两个指针指向的数据
            while (temp1 != null && temp2 != null) {
                if (temp1.data.compareTo(temp2.data) == -1) {
                    newHead.next = temp1;
                    //然后往下挪
                    temp1 = temp1.next;
                } else {
                    newHead.next = temp2;
                    temp2 = temp2.next;
                }
                //6.然新链表的节点往下挪
                newHead = newHead.next;
            }

            //7.判断哪个先到null
            if (temp1 == null) {
                //直接进行拼接
                newHead.next = temp2;
            }
            if (temp2 == null) {
                newHead.next = temp1;
            }
            head = okNewHead.next;
        }

        return head;
    }


    //3、开发一个方法,进行遍历链表
    public void forEach() {
        //1.极端判断
        if (head == null) {
            System.out.println(head);
            return;//并结束方法
        }

        //2.开始进行遍历输出链表中的数据
        //还是保护头结点
        Node<E> temp = head;
        while (temp != null) {
            System.out.print(temp.data + ", ");
            temp = temp.next;
        }
        //进行一次换行
        System.out.println();
    }

}
